// -*- C++ -*-
//
//  This file is part of Siena, a wide-area event notification system.
//  See http://www.inf.usi.ch/carzaniga/siena/
//
//  Authors: Antonio Carzaniga
//  See the file AUTHORS for full details. 
//
//  Copyright (C) 2001-2003 University of Colorado
//
//  This program is free software; you can redistribute it and/or
//  modify it under the terms of the GNU General Public License
//  as published by the Free Software Foundation; either version 2
//  of the License, or (at your option) any later version.
//
//  This program is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU General Public License for more details.
//
//  You should have received a copy of the GNU General Public License
//  along with this program; if not, write to the Free Software
//  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307,
//  USA, or send email to one of the authors.
//
//
// $Id: fwdtable.h,v 1.7 2010-03-11 15:16:45 carzanig Exp $
//
#ifndef SIENA_FWDTABLE_H
#define SIENA_FWDTABLE_H

#include <cstddef>		// for size_t
#include <new>			// for std::bad_alloc

#include "exceptions.h"
#include "forwarding.h"
#include "allocator.h"
#include "stst.h"

namespace siena {

class Interface;
class Selectivity;
class AttributeType;
class ConstraintType;
class Filter;
class CProcessor;

/** @brief implementation of a forwarding table based on an improved
 * "counting" algorithm.
 *
 *  This class implements the index structure and matching algorithm
 *  described in <b>"Forwarding in a Content-Based Network"</b>,
 *  <i>Proceedings of ACM SIGCOMM 2003</i>.
 *  p.&nbsp;163-174. Karlsruhe, Germany.  August, 2003.
 *
 *  <p>In addition, this algorithm includes a number of improvements.
 *  The most notable one uses a fast containment check between the set
 *  of attribute names in the message and the constraint names of a
 *  candidate filter.  If the check is negative, that is, if the set
 *  of attribute names is not a superset of the set of names of a
 *  candidate filter, then the algorithm does not even bother to
 *  "count" the number of matched constraints for that filter.  The
 *  test is based on a representation of the set of names consisting
 *  of a Bloom filter.
 * 
 *  <p>Another improvement uses static counters to implement a faster
 *  but non-reentrant counting algorithm.  This variant can be
 *  selected with the <code>--with-non-reentrant-counters</code>
 *  option at configure-time.
 */
class FwdTable : public ForwardingTable {
public:
    FwdTable() throw();

    virtual ~FwdTable() throw();

    virtual void ifconfig(if_t, const predicate &) throw(bad_constraint,
							 std::bad_alloc);
    virtual void consolidate() throw();

    virtual void match(const message &, MatchHandler &) const throw();
    virtual void match(const message &, MatchMessageHandler &) const throw();

    virtual void clear() throw();
    virtual void clear_recycle() throw();

    virtual size_t allocated_bytesize() const throw();
    virtual size_t bytesize() const throw();

    /** @brief Determines the number of pre-processing rounds applied to
     *	every message.
     **/
    void set_preprocess_rounds(unsigned int) throw();

    /** @brief Returns the current number of pre-processing rounds.
     **/
    unsigned int get_preprocess_rounds() const throw();

private:
    /** @brief Private allocator of the forwarding table.  
     *
     *  All the data structure forming the forwarding table are
     *  allocated through this memory management system.
     **/
    FTAllocator		memory;

    /** @brief Private allocator for temporary storage used by the
     *  forwarding table.
     *
     *  All the data volatile, temporary data structures used by the
     *  forwarding table are allocated through this memory management
     *  system.
     **/
    FTAllocator		tmp_memory;

    /** @brief Total number of interfaces associated with a predicate in the
     *  forwarding table.
     **/
    ifid_t		if_count;

    /** @brief Total number of filters in the forwarding table.
     **/
    unsigned int	f_count;

    /** @brief Number of pre-processing rounds
     **/
    unsigned int	preprocess_rounds;

    /** @brief Main index of constraints
     **/
    STST		attributes;

    /** @brief First element in the selectivity table
     *
     *  This is the element with the highest selectivity level.  In
     *  other words, this is the constraint name that, if not present
     *  in the message, can exclude the higher number of interfaces.
     **/
    Selectivity *	selectivity_first;

    /** @brief Last element in the selectivity table
     *
     *  This is the element with the lowest selectivity level.
     **/
    Selectivity *	selectivity_last;

    /** @brief Adds a new item to the selectivity table.
     *
     *  The selectivity table is a double-link list of
     *  \c Selectivity objects.  The list is sorted according to
     *  the level of selectivity, which correspond to the size of the
     *  \p exclude set.
     *
     *  <p>When a new selectivity item is created, it is added at the
     *  bottom of the list, having selectivity level 1.
     **/
    Selectivity	*	new_selectivity(const string_t &, ifid_t) throw();

    /** @brief Adds an interface to the set of excluded interfaces of
     *	an existing item in the selectivity table
     *
     *  When a new interface is added to the <code>exclude</code> set
     *  of a selectivity item of a given name, that item is moved
     *  along the selectivity list in order to maintain the list
     *  sorted by level of selectivity.  This is done by shifting the
     *  item as in a bubble-sort algorithm.
     **/
    void		add_to_selectivity(Selectivity *, ifid_t) throw();

    /** @brief Utility function that finds an attribute in the
     *	constraint index 
     **/
    AttributeType *		get_attribute(const string_t & name) throw();

    /** @brief Utility function that connects a constraint descriptor
     *  to the descriptor of the filter containing that constraint
     **/
    void		connect(ConstraintType *, Filter *, const string_t &) throw();

    struct attr_descr_link {
	AttributeType * a;
	attr_descr_link * next;
    };
    attr_descr_link * consolidate_list;
};

} // end namespace siena

#endif
